package org.example.string;

public class ExpandAroundCenter {
    /**
     * 最长回文子串，找出字符串中的最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n == 1)
            return s;
        //每次找到最大回文子串的起始和结尾
        int start = 0, end = 0;
        //固定一个中心点,双指针向外扩展
        for (int i = 0; i < n; i++) {
            //奇数情况
            int len1 = expandAroundCenter(s,i,i);
            //偶数情况
            int len2 = expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len>end-start+1){
                start=i-(len-1)/2;
                end=i+len/2;
            }
        }
        return s.substring(start, end + 1);
    }

    /**
     * 以中心点向左右移动双指针寻找回文字符串
     * @param s
     * @param left
     * @param right
     * @return
     */
    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 返回回文长度
        return right - left - 1;
    }
}
